<?php
/**
 * 二分搜索树
 *
 * 二分搜索树是一个二叉树，
 * 不一定是一颗完全二叉树，
 * 和堆(完全二叉树)不一样，不能用数组表示,只能用节点来表示
 *
 * 性质：
 * (1) 每个节点的键值大于左孩子
 * (2) 每个节点的键值小于右孩子
 * (3) 以左右孩子为根的子树仍为二分搜索树
 */

/**
 * 节点类
 */
class Node
{
    public $key;
    public $value;
    public $left;
    public $right;
    
    public function __construct($key,$value)
    {
        $this->key   = $key;
        $this->value = $value;
        $this->left  = $this->right = NULL;
    }
    
}

/**
 * 二分搜索树
 */
class BST
{
    public $root;
    public $count;
    
    public function __construct($node=NULL)
    {
        $this->root = $node;
        $this->count = 0;
    }
    
    /**
     * 长度
     */
    public function size()
    {
        return $this->count;
    }
    
    /**
     * 判断是否为空
     */
    public function isEmpty()
    {
        return $this->count == 0;
    }
    
    /**
     * 插入
     */
    public function insert($key,$vlaue)
    {
        $this->root = $this->_insert($this->root,$key,$vlaue);
    }
    
    /**
     * 递归插入
     */
    private function _insert($node,$key,$value)
    {
        //如果node为空，则新创建一个新节点
        if ($node == NULL)
        {
            $this->count++;
            return new Node($key,$value);
        }
        
        if ($key == $node->key)
        {
            $node->value = $value;
        }
        elseif($key > $node->key)
        {
            $node->right = $this->_insert($node->right,$key,$value);
        }
        else
        {
            $node->left = $this->_insert($node->left,$key,$value);
        }
        
        return $node;
    }
    
    /**
     *查看node为根的二分搜索树中是否包含键值为key的节点
     */
    public function contain($key)
    {
        return $this->_contain($this->root,$key);
    }
    private function _contain($node,$key)
    {
        if ($node == NULL)
        {
            return false;
        }
        
        if ($key == $node->key)
        {
            return true;
        }
        elseif($key > $node->key)
        {
            return $this->_contain($node->right,$key);
        }
        else
        {
            return $this->_contain($node->left,$key);
        }
        
        
    }
    
    /**
     *查看node为根的二分搜索树中键值为key的节点的值
     */
    public function search($key)
    {
        return $this->_search($this->root,$key);
    }
    private function _search($node,$key)
    {
        if ($node == NULL)
        {
            return false;
        }
        
        if ($key == $node->key)
        {
            return $node->value;
        }
        elseif($key > $node->key)
        {
            return $this->_search($node->right,$key);
        }
        else
        {
            return $this->_search($node->left,$key);
        }
    }
    
    /**
     * 前序
     */
    public function preOrder()
    {
        $this->_preOrder($this->root);
    }
    private function _preOrder($node)
    {
        if ($node != NULL)
        {
            var_dump($node->key);
            $this->_preOrder($node->left);
            $this->_preOrder($node->right);
        }
    }
    
    /**
     * 中序
     */
    public function inOrder()
    {
        $this->_inOrder($this->root);
    }
    private function _inOrder($node)
    {
        if ($node != NULL)
        {
            $this->_inOrder($node->left);
            var_dump($node->key);
            $this->_inOrder($node->right);
        }
    }
    
    /**
     * 后序
     */
    public function postOrder()
    {
        $this->_postOrder($this->root);
    }
    private function _postOrder($node)
    {
        if ($node != NULL)
        {
            $this->_postOrder($node->left);
            $this->_postOrder($node->right);
            var_dump($node->key);
        }
    }
    
    /**
     * 层序遍历
     */
    public function levelOrder()
    {
        $queue = new SplQueue();
        $queue->push($this->root);
        while(!$queue->isEmpty())
        {
            $node = $queue->bottom();
            var_dump($queue->pop()->key);
            
            if ($node->left)
            {
                $queue->push($node->left);
            }
            
            if ($node->right)
            {
                $queue->push($node->right);
            }
        }
    }
    
    /**
     * 返回最小键值的节点
     */
    public function minMum()
    {
        $node = $this->_minMum($this->root);
        return $node->key;
    }
    private function _minMum($node)
    {
        if ($node->left == NULL)
        {
            return $node;
        }
        $this->_minMum($node->left);
    }
    
    /**
     * 返回最大键值的节点
     */
    public function maxMum()
    {
        $this->root = $this->_maxMum($this->root);
        return $this->root->key;
    }
    private function _maxMum($node)
    {
        if ($node->right == NULL)
        {
            return $node;
        }
        $this->_maxMum($node->right);
    }
    
    /**
     * 删除二分搜索树的最小节点
     * 并返回新的根节点
     */
    public function removeMin()
    {
        if ($this->root)
        {
            $node = $this->_removeMin($this->root);
        }
    }
    private function _removeMin($node)
    {
        if ($node->left == NULL)
        {
            $right_node = $node->right;
            $this->count--;
            return $right_node;
        }
        
        $node->left = $this->_removeMin($node->left);
        return $node;
    }
    
    /**
     * 删除二分搜索树的最大节点
     * 并返回新的根节点
     */
    public function removeMax()
    {
        if ($this->root)
        {
            $node = $this->_removeMax($this->root);
        }
    }
    private function _removeMax($node)
    {
        if ($node->right == NULL)
        {
            $left_node = $node->left;
            $this->count--;
            return $left_node;
        }
        
        $node->right = $this->_removeMax($node->right);
        return $node;
    }
    
    /**
     * 删除二分搜索树键值为key的节点
     */
    public function remove($key)
    {
        return $this->_remove($this->root,$key);
    }
    private function _remove($node,$key)
    {
        if ($node == NULL)
        {
            return NULL;
        }
        
        if ($key > $node->key)
        {
            $node->right = $this->_remove($node->right,$key);
            return $node;
        }
        elseif($key < $node->key)
        {
            $node->left = $this->_remove($node->left,$key);
            return $node;
        }
        else
        {
            if ($node->left == NULL)
            {
                $right_node = $node->right;
                $this->count--;
                return $right_node;
            }
            
            if ($node->right == NULL)
            {
                $left_node = $node->left;
                $this->count--;
                return $left_node;
            }
            
            #左右孩子同时存在的情况下，
            #思路：找到待删除节点的左子树的最大节点或者右子树的最小节点进行替换
            
            //找到左子树的最大节点作为前驱节点，或者右子树的最小节点作为后继节点 $s = $this->_minMum($node->right)
            $s = $this->_maxMum($node->left);
            
            //此时新增一个节点，conut++;
            $this->count++;
            
            //移除左子树的最大节点并得到左子树新的根节点，
            $s->left = $this->_removeMax($node->left);
            $s->right  = $node->right;
            
            $this->count--;
            
            return $s;
        }
    }
}

$bst = new BST();

//添加
for($i=1;$i<10;$i++)
{
    $bst->insert($i,$i);
}

#删除指定节点
var_dump($bst->remove(5));

#查看节点是否存在
var_dump($bst->contain(5));

#查询节点的值
var_dump($bst->search(5));

#前序
var_dump($bst->preOrder());

#中序
var_dump($bst->inOrder());

#后序
var_dump($bst->postOrder());

#层序
var_dump($bst->levelOrder());

#找到最小的节点
var_dump($bst->minMum());

#找到最大的节点
var_dump($bst->maxMum());

#删除最小的节点
var_dump($bst->removeMin());

#删除最大的节点
var_dump($bst->removeMax());




